The present disclosure relates to a general unified paging method for translation tables. In particular, the present disclosure relates to storing the bulk of translation structures in a storage system, while keeping a small subset in the memory. Still more particularly, the present disclosure relates to addressing a large translation structure in limited flash memory.
A flash device due to erase-before-write characteristic needs a dynamic translation table that keeps track of latest mapping of a logical block to physical block. As and when logical blocks are overwritten, the translation table is updated to point to the new physical block and the old physical blocks are reclaimed by a process known as garbage collection.
Translation tables can be implemented differently for different use cases and can be broadly classified as dense and sparse. A dense translation table optimizes memory consumption based on the usage pattern where a range of logical blocks is populated. The dense translation table utilizes contiguous memory for a range of blocks and uses the logical block numbers (or transformations thereof) as indices into the table. Sparse translation tables, on the other hand, are exemplified by a large (say, 64 bit or higher) address range that is sparsely populated without a discernible pattern. Index based lookups are less attractive compared to hash and match type data structures and each logical block number is explicitly stored as part of translation table entry to enable the match based lookups. Depending on the system implementation, translation tables can be used to store additional per block information (besides the logical to physical translation) such as CRC, access statistics, and the like.
The total size of the translation data structure (or table) in a storage system is governed by the expected number of translation entries, size of each entry, and data structure requirements. As the storage capacity continues to increase fueled by storage density increases, large aggregations of devices, data reduction technologies like compression, and enhanced use cases, the translation data structures may reach sizes where it is not feasible (technologically or economically) to store the entire structure in the memory (DRAM). The translation process is critical to the storage device performance and reliability. Therefore, there remains a need for a system that resolves the conflict presented by the need for quick and reliable access to the translation tables and while limiting the amount of memory (DRAM) that it consumes.